| Group theory |
|---|
| Group theory |
|
Cyclic group Zn
Symmetric group, Sn Dihedral group, Dn Alternating group An Mathieu groups M11, M12, M22, M23, M24 Conway groups Co1, Co2, Co3 Janko groups J1, J2, J3, J4 Fischer groups F22, F23, F24 Baby Monster group B Monster group M |
|
|
|
Solenoid (mathematics)
Circle group General linear group GL(n) Special linear group SL(n) Orthogonal group O(n) Special orthogonal group SO(n) Unitary group U(n) Special unitary group SU(n) Symplectic group Sp(n) Lorentz group Poincaré group Conformal group Diffeomorphism group Loop group Infinite-dimensional Lie groups O(∞) SU(∞) Sp(∞) |
In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). Note that the group of all permutations of a set is the symmetric group; the term permutation group is usually restricted to mean a subgroup of the symmetric group. The symmetric group of n elements is denoted by Sn; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).
The application of a permutation group to the elements being permuted is called its group action; it has applications in both the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry.
Contents |
As a subgroup of a symmetric group, all that is necessary for a permutation group to satisfy the group axioms is that it contain the identity permutation, the inverse permutation of each permutation it contains, and be closed under composition of its permutations. A general property of finite groups implies that a finite subset of a symmetric group is again a group if and only if it is closed under the group operation.
Permutations are often written in cyclic form[1] so that given the set M = {1,2,3,4}, a permutation g of M with g(1) = 2, g(2) = 4, g(4) = 1 and g(3) = 3 will be written as (1,2,4)(3), or more commonly, (1,2,4) since 3 is left unchanged; if the objects are denoted by a single letter or digit, commas are also dispensed with, and we have a notation such as (1 2 4).
Consider the following set G of permutations of the set M = {1,2,3,4}:
G forms a group, since aa = bb = e, ba = ab, and baba = e. So (G,M) forms a permutation group.
The Rubik's Cube puzzle is another example of a permutation group. The underlying set being permuted is the coloured subcubes of the whole cube. Each of the rotations of the faces of the cube is a permutation of the positions and orientations of the subcubes. Taken together, the rotations form a generating set, which in turn generates a group by composition of these rotations. The axioms of a group are easily seen to be satisfied; to invert any sequence of rotations, simply perform their opposites, in reverse order.[3]
The group of permutations on the Rubik's Cube does not form a complete symmetric group of the 20 corner and face cubelets; there are some final cube positions which cannot be achieved through the legal manipulations of the cube.
More generally, every group G is isomorphic to a subgroup of a permutation group by virtue of its regular action on G as a set; this is the content of Cayley's theorem.
If G and H are two permutation groups on the same set X, then we say that G and H are isomorphic as permutation groups if there exists a bijective map f : X → X such that r ↦ f −1 o r o f defines a bijective map between G and H; in other words, if for each element g in G, there is a unique hg in H such that for all x in X, (g o f)(x) = (f o hg)(x). This is equivalent to G and H being conjugate as subgroups of Sym(X). In this case, G and H are also isomorphic as groups.
Notice that different permutation groups may well be isomorphic as abstract groups, but not as permutation groups. For instance, the permutation group on {1,2,3,4} described above is isomorphic as a group (but not as a permutation group) to {(1)(2)(3)(4), (12)(34), (13)(24), (14)(23)}. Both are isomorphic as groups to the Klein group V4.
A 2-cycle is known as a transposition. A simple transposition in Sn is a 2-cycle of the form (i i + 1).
For a permutation p in Sn, a pair (i , j)∈In is a permutation inversion, if when i<j , we have p(i) > p(j).[4]
Every permutation can be written as a product of simple transpositions; furthermore, the number of simple transpositions one can write a permutation p in Sn can be the number of inversions of p and if the number of inversions in p is odd or even the number of transpositions in p will also be odd or even corresponding to the oddness of p.